package com.leetcode.algorithm.y22.m06;

/**
 * 
 * 376. 摆动序列
 * 
 * https://leetcode.cn/problems/wiggle-subsequence/
 * 
 * @author jie.deng
 *
 */
class Question0376Solution01 {
	
	public int wiggleMaxLength(int[] nums) {
		int len = nums.length;
		// DP状态定义
		int[][] dp = new int[len][2];

		// DP状态初始化
		// dp[i][0] 表示nums[0...i] 以nums[i]结尾，摆动序列末段为上升段 的 最长子序列的长度
		// dp[i][0] 表示nums[0...i] 以nums[i]结尾，摆动序列末段为下降段 的 最长子序列的长度
		dp[0][0] = 1;
		dp[0][1] = 1;

		int maxLen = 1;
		// DP状态转移方程
		for (int i = 1; i < len; i++) {
			if (nums[i] > nums[i - 1]) {
				dp[i][0] = Math.max(dp[i - 1][1] + 1, dp[i - 1][0]);
			} else if (nums[i] < nums[i - 1]) {
				dp[i][1] = Math.max(dp[i - 1][0] + 1, dp[i - 1][1]);
			} else {
				dp[i][0] = dp[i - 1][0];
				dp[i][1] = dp[i - 1][1];
			}
			maxLen = Math.max(maxLen, Math.max(dp[i][0], dp[i][1]));
		}
		return maxLen;
	}
    
}